// 本题测试链接:
// https://lightoj.com/problem/internet-bandwidth
// 这是一道DinicAlgorithm算法的题
// 把如下代码粘贴进网页所提供的java编译器环境中
// 不需要修改任何内容可以直接通过
// 请看网页上的题目描述并结合main函数的写法去了解这个模板的用法

package com.tys.algorithm.advanced.code.class47;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Code03_DinicAlgorithm {

    //有向边
    public static class Edge {
        public int from; //起点
        public int to; //终点
        public int available; //可用额度

        public Edge(int a, int b, int c) {
            from = a;
            to = b;
            available = c;
        }
    }

    public static class Dinic {
        //有多少点
        private int N;
        //起始点对应的在edges中的序号数组
        private ArrayList<ArrayList<Integer>> nexts;
        //边数组
        private ArrayList<Edge> edges;
        //高度数组
        private int[] depth;
        //记录从哪条边开始试：边的序号
        private int[] cur;

        public Dinic(int nums) {
            N = nums + 1; //自动扩1个点:有些0开始，有些1开始
            //初始化边数据组
            nexts = new ArrayList<>();
            for (int i = 0; i <= N; i++) {
                nexts.add(new ArrayList<>());
            }
            edges = new ArrayList<>();
            depth = new int[N];
            cur = new int[N]; //
        }

        //加边：u->v 的边可用额度 r
        public void addEdge(int u, int v, int r) {
            int m = edges.size(); //当前边的个数:0开始
            //加u->v的边，可用额度r
            edges.add(new Edge(u, v, r));
            //设置u的序号
            nexts.get(u).add(m);
            //加u->v的反向边v->，可用额度0
            edges.add(new Edge(v, u, 0));
            //设置v的序号
            nexts.get(v).add(m + 1);
        }

        //求s->t的最大流量
        public int maxFlow(int s, int t) {
            int flow = 0;
            //宽度优先遍历，s->t 不能到则退出
            while (bfs(s, t)) {
                //s->t一定能到
                //cur填充0：初始从0开始试
                Arrays.fill(cur, 0);
                //计算流量：默认目标无穷大
                flow += dfs(s, t, Integer.MAX_VALUE);
                //depth填充0
                Arrays.fill(depth, 0);
            }
            return flow;
        }

        //宽度优先遍历：得到各个节点高度数组
        //s->t：宽度优先遍历，s层永远0层
        //标记t能不能到
        //标记高度，所有点高度重新算
        private boolean bfs(int s, int t) {
            //队列
            LinkedList<Integer> queue = new LinkedList<>();
            queue.addFirst(s); //s入队列
            //标记所有点是否已经去过
            boolean[] visited = new boolean[N];
            //初始s标记去过
            visited[s] = true;
            //遍历队列：
            while (!queue.isEmpty()) {
                //弹出队列尾数据
                int u = queue.pollLast();
                //遍历以u开始的节点的所有边：记录所有子节点的高度，当前高度+1
                for (int i = 0; i < nexts.get(u).size(); i++) {
                    //得到边
                    Edge e = edges.get(nexts.get(u).get(i));
                    //去哪里
                    int v = e.to;
                    //v没有去过 && 有可用额度，可到达
                    if (!visited[v] && e.available > 0) {
                        visited[v] = true; //v去过了
                        depth[v] = depth[u] + 1; //v的高度=u高度+1
                        if (v == t) { //到最后了
                            break;
                        }
                        //将v加入队列
                        queue.addFirst(v);
                    }
                }
            }
            //返回t是否已经去过
            return visited[t];
        }

        //深度优先遍历
        // s->t
        // s: 当前来到了s点，s可变
        // t: 最终目标是t，t固定参数
        // r: 收到的任务：经过相减后剩余的
        // 收集到的流，作为结果返回，ans <= r
        private int dfs(int s, int t, int r) {
            //到t || 没任务了
            if (s == t || r == 0) {
                return r;
            }
            int f = 0;
            int flow = 0;
            // 跳过使用完的，s点从哪条边开始试 -> cur[s]
            for (; cur[s] < nexts.get(s).size(); cur[s]++) {
                //cur[s]: 从s的哪个边开始
                // 得到s的开始边序号
                int ei = nexts.get(s).get(cur[s]);
                Edge e = edges.get(ei); //得到当前边
                Edge o = edges.get(ei ^ 1); //反向边
                //下个节点高度=比当前节点高度+1 && 递归求下级节点到t的最大，任务是当前额度和给定任务r的最小值
                if (depth[e.to] == depth[s] + 1 && (f = dfs(e.to, t, Math.min(e.available, r))) != 0) {
                    e.available -= f; //当前额度减f
                    o.available += f; //当前反向边额度加f
                    flow += f; //完成的流
                    r -= f; //任务减f
                    //任务完成退出循环
                    if (r <= 0) {
                        break;
                    }
                }
            }
            //返回最大值
            return flow;
        }
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int cases = cin.nextInt();
        for (int i = 1; i <= cases; i++) {
            int n = cin.nextInt();
            int s = cin.nextInt();
            int t = cin.nextInt();
            int m = cin.nextInt();
            Dinic dinic = new Dinic(n);
            for (int j = 0; j < m; j++) {
                int from = cin.nextInt();
                int to = cin.nextInt();
                int weight = cin.nextInt();
                dinic.addEdge(from, to, weight);
                dinic.addEdge(to, from, weight);
            }
            int ans = dinic.maxFlow(s, t);
            System.out.println("Case " + i + ": " + ans);
        }
        cin.close();
    }

}